public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        // String s = "aaa";
        // System.out.println(test.countSubstrings(s));

        String s = "babad";
        System.out.println(test.longestPalindrome(s));
    }

    public int countSubstrings(String s) {
        /**
         * 回文子串
         * 状态表示：
         *   dp[i][j]表示以i元素为开头，以j元素为结尾的子字符串是否是回文字符串
         * 状态转移方程：
         *   // 首先要保证首位字符串相同
         *   if(s.charAt(i) == s.charAt(j)) {
         *       // 两个字符相邻或相等，此时为回文，或者向内缩进为回文
         *       if(i + 1 >= j || dp[i+1][j-1]) {
         *           dp[i][j] = true;
         *       }
         *   }
         * 初始化：
         *   将i == j的位置初始化为 true
         * 填表顺序：
         *   从下到上，从左到右
         * */
        // 1 预处理
        int n = s.length();
        // 2 创建dp表
        boolean[][] dp = new boolean[n][n];
        // 3 初始化
        for(int k = 0; k < n; k++) {
            dp[k][k] = true;
        }
        // 4 填表
        int count = n;
        for(int i = n-1; i >= 0; i--) {
            for(int j = i+1; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    // 两个字符相邻或相等，此时为回文，或者向内缩进为回文
                    if(i + 1 == j || dp[i+1][j-1]) {
                        dp[i][j] = true;
                        count++;
                    }
                }
            }
        }
        // 5 返回值
        return count;
    }

    public String longestPalindrome(String s) {
        /**
         * 最长回文子串
         * */
        // 1 预处理
        int n = s.length();
        // 2 创建dp表
        boolean[][] dp = new boolean[n][n];
        // 3 初始化
        for(int k = 0; k < n; k++) {
            dp[k][k] = true;
        }
        // 4 填表
        int maxLength = 1;
        int[] maxLengthIndexList = new int[]{0,1};
        for(int i = n-1; i >= 0; i--) {
            for(int j = i+1; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    // 两个字符相邻或相等，此时为回文，或者向内缩进为回文
                    if(i + 1 == j || dp[i+1][j-1]) {
                        dp[i][j] = true;
                        // -若是最长长度，则更新最长长度并存储其下标
                        if(j - i + 1 > maxLength) {
                            maxLength = j - i + 1;
                            maxLengthIndexList = new int[]{i, j+1};
                        }
                    }
                }
            }
        }
        // 5 返回值
        return s.substring(maxLengthIndexList[0], maxLengthIndexList[1]);
    }
}
